package vivo;

import java.util.Scanner;

/**
 * there are many balls .find the weighter ball get the time that find the
 * weighter ball(max time)
 */
public class WeightestBall {

    /**
     * assign group 将n个数分成m组
     */
    private static void assignGroup(int[] array, int n, int m) {
        if (n < 2)
            return;
        if (m == 3) {
            if (n % 3 == 0) {
                array[0] = array[1] = array[2] = n / 3;
            } else {
                array[0] = n / 3 + 1;
                /* 剩余的2组继续通过回调赋值 */
                assignGroup(array, n - (n / 3 + 1), 2);
            }
        }
        if (m == 2) {
            if (n % 2 == 0) {
                array[1] = array[2] = n / 2;
            } else {
                array[1] = n / 2 + 1;
                array[2] = n - array[1] - array[2];
            }
        }
        System.out.println("\nassgin group result");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * compare and get the time 找出最重一个球所需的次数
     */
    private static int getMaxWeight(int[] array) {
        int result = 0;
        /* 1 sort: small->big */
        // sort(array);
        int i = array[0], j = array[1], k = array[2];
        if (i == j && j == k) {
            result = 1 + f(i);
        } else {
            /* 这里会有区别：这里可以求出得到质量不同球的最大/最小次数：此处求最小次数 */
            if (f(i) <= f(k))
                result = 1 + f(i);
            else
                result = 1 + f(k);
        }
        System.out.println("\nneed the least " + result + " times");
        return result;
    }

    /**
     * f():关键的递归回调函数：按照同样的规则逐层求出所需的次数
     */
    private static int f(int n) {
        int result = 0;
        if (n == 2)
            return 1;
        if (n == 1)
            return 0;
        int[] array = new int[3];
        assignGroup(array, n, 3);
        result = getMaxWeight(array);
        return result;
    }

    /**
     * sort 排序：按照从小到大的顺序排列数组
     */
    private static void sort(int[] array) {
        /* select sort:选择排序 */
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
        System.out.println("\nsort result");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static void main(String[] args) {
        System.out.println("please input the ball number:");
        @SuppressWarnings("resource")
        int num = new Scanner(System.in).nextInt();
        int[] array = new int[3];
        if (num > 2) {
            assignGroup(array, num, 3);
            getMaxWeight(array);
        }
    }
}